Playing with GF(3²)

(Last Mod: 27 November 2010 21:38:01 )

Introduction
Establish a suitable finite field for GF(3²)

Introduction

In most applications where a Galois field is employed it is of the form GF(2ⁿ). The main reason is convenience. Since math on the polynomial coefficients is done in GF(2), the operations can be converted to binary logic circuits very readily. Furthermore, since there are exactly 2ⁿ symbols, those symbols can be represented by the 2ⁿ possible bit patterns in an n-bit word. However, these conveniences can mask some of the subtler points of Galois Fields and so this page will work with a slightly more complex Galois Field, namely GF(3²), in order to make some of those points more apparent.

It is assumed that the you have either worked through the page on Polynomial Arithmetic in GF(pⁿ) or you will be doing so in parallel with this page. To make this easier, this page is laid in a similar fashion.

Establish a suitable finite field for GF(3²)

Recall from the discussion of finite fields, that a finite field is an algebra consisting of a set of elements and two operators that act on those elements. We are free to define the elements and the operators in any way we choose provided the properties required of a finite field are satisfied. Those requirements are:

The set must be an abelian group with respect to the first operator.
The set, less the identity element for the first operator, must be an abelian group with respect to the second operator.
The second operator must be distributive over the first operator.

Further recall that to be an abelian group, the following properties must hold with respect to the operator:

The set must be closed.
The set must be commutative.
The set must be associative.
The set must possess an identity element.
The set must possess an inverse for every element in the set.

The elements of GF(3²)

There are nine symbols in GF(3²) which we can represent as the following polynomials:

Elementary Polynomials in GF(3²)

Symbol	Polynomial
00	0
01	1
02	2
10	D
11	D+1
12	D+2
20	2D
21	2D+1
22	2D+2

The primitive polynomials in GF(3²)

We also need a "primitive polynomial" which, for GF(pⁿ) is a polynomial of order n that cannot be evenly divided by a polynomial of degree less than n. We do not consider the cases for dividing the candidate polynomial by 0 or 1 for obvious reasons (division by 0 is undefined and division by 1 is always possible).

Since primitive polynomials must be irreducible, the high order coefficient must be one and the constant coefficient must be non-zero. In GF(3²) this leaves us with only the following six candidates.

Candidate Primitive Polynomials in GF(3²)

Symbol	Polynomial
101	D² + 1
102	D² + 2
111	D² + D+1
112	D² + D+2
121	D² + 2D+1
122	D² + 2D+2

We could examine each of the candidate polynomials in turn and divide it by each of the potentially irreducible polynomials of order less than n, of which there are only two.

Lower Order Irreducible Polynomials <2 in GF(3²)

Symbol	Polynomial
11	D+1
12	D+2

With so few candidates for primitive polynomials and so few lower order irreducible polynomials to work with, an exhaustive search of the space is very straightforward. We will examine three candidates using this approach before turning to the other approach.

Primitive polynomials by direct test

Example: Is 101 (D² + 1) a primitive polynomial in GF(3²)

Dividing D² + 1 by D + 1 yields D + 2 with a remainder of 2.

Dividing D² + 1 by D + 2 yields D + 1 with a remainder of 2.

Since both have non-zero remainders, D² + 1 is an irreducible polynomial.

The question now is whether D² + 1 is primitive.

One way to show this is that the smallest value for which D² + 1 evenly divides D^m - 1 is m = pⁿ - 1 = 8.

A comparable way is to show that D^k generates all of the polynomials in the set. We will pursue this latter course.

k D^k Polynomial Symbol

0 D⁰ 1 01

1 D¹ D 10

2 D² 2 02

3 D³ 2D 20

4 D⁴ 1 01

5 D⁵ D 10

6 D⁶ 2 02

7 D⁷ 2D 20

8 D⁸ 1 01

As can be seen, not all of the polynomials in the set are generated as evidenced by D⁴ generating 1 again and hence creating a cycle of generated polynomials with period of 4. So, while D² + 1 divides D⁸ - 1, also also divides D⁴ - 1.

Therefore, 101 (D² + 1) is not a primitive polynomial in GF(3²).

Example: Is 102 (D² + 2) a primitive polynomial in GF(3²)

Dividing D² + 2 by D + 1 yields D + 2 with no remainder.

Hence D² + 2 is reducible and need not be explored further.

Therefore, 102 (D² + 2) is not a primitive polynomial in GF(3²).

Example: Is 112 (D² + D + 1) a primitive polynomial in GF(3²)

Dividing D² + D + 2 by D + 1 yields D with a remainder of 2.

Dividing D² + D + 2 by D + 2 yields D + 2 with a remainder of 1.

Since both have non-zero remainders, D² + D + 2 is an irreducible polynomial.

The question now is whether D² + D + 2 is primitive. As before, we will see if D^k generates the entire set under this modulus.

k D^k Polynomial Symbol

0 D⁰ 1 01

1 D¹ D 10

2 D² 2D + 1 21

3 D³ 2D + 2 22

4 D⁴ 2 02

5 D⁵ 2D 20

6 D⁶ 1D + 2 12

7 D⁷ D + 1 11

8 D⁸ 1 01

As can be seen, all of the polynomials in the set are generated, as evidenced by D⁸ being the first time (after D⁰) that 1 is generated.

Therefore, 112 (D² + D + 2) is a primitive polynomial in GF(3²).

Primitive polynomials by elimination

The other approach is to finding the irreducible polynomials is to first produce a list of all of the candidate degree-n primitive polynomials and then multiply all of the lower degree polynomials together to produce all of the non-irreducible polynomials of degree n and eliminate these from the list. The initial list is the same as in the previous approach, namely:

Candidate Primitive Polynomials in GF(3²)

Symbol	Polynomial
101	D² + 1
102	D² + 2
111	D² + D+1
112	D² + D+2
121	D² + 2D+1
122	D² + 2D+2

In the case of n=2, the polynomials of degree less than n can be written in the form

aD + b

Multiplying two such polynomials together, our candidate primitive polynomials may be written in the form

P = (aD + b)(cD + d)

P = (ac)D² + (ad+bc)D + (bd)

If we were to approach this blindly, we would have to examine 81 possibilities. However, we note that since primitive polynomials must be of order n, that neither a nor c may be zero. This immediately reduces the search space to 36. We also know that the order n coefficient must be exactly 1 which means that a and c must be multiplicative inverses of each other in GF(3). But we have also established that if the high order coefficient is anything greater than 1 that the polynomial is reducible, hence we can restrict our examination to lower order polynomials having an high order coefficient of 1. This means that a and c must both be exactly 1 which simplifies the form of our primitive polynomials to:

P = (D + b)(D + d)

P = D² + (d+b)D + (bd)

This collapses our search space to only 9 entries and if we impose the requirement that primitive polynomials must have a non-zero constant term then we have reduced it to 4. While this is already quite manageable, we can reduce it even further my nothing that multiplication in any field is commutative and therefore if we order the elements of our set (in any way we choose) then we can limit ourselves to only evaluating those expressions in which the second factor is greater than or equal to the first factor. The result is that we now only have to evaluate 3 expressions. Notice that a little bit of thought up front has saved us 96% of the work.

Candidate Primitive Polynomials that are Reducible in GF(3²)

b	d	b+d	bd	P	symbol
1	1	2	1	D²+2D+1	121
1	2	0	2	D²+2	102
2	2	1	1	D²+D+1	111

After eliminating these from the original list, we now have the complete list of polynomials of degree n that are irreducible. There are now only three remainingcandidates for being primitive polynomials in GF(3²):

Irreducible Candidates for Primitive Polynomials in GF(3²)

Symbol	Polynomial
101	D² + 1
112	D² + D+2
122	D² + 2D+2

The only remaining task is to see which of these three is/are actually primitive. We have the same tools as with the prior approach and might as well note that two of the three (101 and 112) were evaluated previously with the result that 101 is not primitive while 112 is. At this point we could either go ahead and check 122 to see if it is primitive or we could check how many primitive polynomials there are in GF(3²) and let that guide us. Let's do both.

In GF(32), the number of primitive polynomials is exactly given by

N = totient(pⁿ-1)/n = 2

Since there are exactly two primitive polynomials and since we have identified only one and have only one candidate remaining, we can conclude that 122 should be a primitive polynomial; iif it isn't, then we know we have made an error somewhere. We will now verify that 122 is, indeed, primitive by seeing if it generates the entire set of polynomials under this modulus.

k	D^k	Polynomial	Symbol
0	D⁰	1	01
1	D¹	D	10
2	D²	D + 1	11
3	D³	2D + 1	21
4	D⁴	2	02
5	D⁵	2D	20
6	D⁶	2D + 2	22
7	D⁷	D + 2	12
8	D⁸	1	01

Multiplicative inverses in GF(3²)

Now that we have found at least one primitive polynomial with which to define multiplication in our finite field, let us turn our attention to determining the multiplicative inverses of each non-zero element in our set. For convenience, since the table is directly above, let's use 122 as our primitive polynomial.

Since each polynomial maps to an integer power of D and since D⁸ is 1, we can use the fact that two polynomials are multiplicative inverses if the exponents in their exponential representations add to 8. Hence

Multiplicative Inverses in GF(3²) mod 112

k	D^k	Polynomial	Symbol	(D^k)^-1	Polynomial	Symbol
0	D⁰	1	01	D⁸	1	01
1	D¹	D	10	D⁷	D + 2	12
2	D²	D + 1	11	D⁶	2D + 2	22
3	D³	2D + 1	21	D⁵	2D	20
4	D⁴	2	02	D⁴	2	02
5	D⁵	2D	20	D³	2D + 1	21
6	D⁶	2D + 2	22	D²	D + 1	11
7	D⁷	D + 2	12	D¹	D	10

Playing with GF(32)

Playing with GF(3²)